package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/5 16:12
 */
public class J51 {

    // https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
    // 双重循环解
    public static int reversePairs(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[j] > nums[i]) {
                    count++;
                }
            }
        }
        return count;
    }

    // 归并排序, 归并过程中, 如果左边回去的时候不统计, 右边回去的过程中统计左边还有多少个比他大的. 前提是左右都是有序数组了
    public static int reversePairs2(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        return process(nums, 0, nums.length - 1);
    }

    public static int process(int[] arr, int l, int r) {
        if(l == r) {
            return 0;
        }
        int mid = l + ((r-l) >> 1);
        int leftPair = process(arr, l, mid);
        int rightPair = process(arr, mid+1, r);
        if(arr[mid] < arr[mid+1]) {
            return leftPair+rightPair;
        }
        int pair = merge(arr, l, mid, r);
        return leftPair + rightPair + pair;
    }

    private static int merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int index = 0, lIndex = l, rIndex = mid + 1;  // index 辅助数组的赋值下标， lIndex：左边下标，rIndex：右边下标
        int count = 0;
        while (lIndex <= mid && rIndex <= r) {
        // help[index++] = arr[lIndex] < arr[rIndex] ? arr[lIndex++] : arr[rIndex++];
            if(arr[lIndex] <= arr[rIndex]) {
                help[index++] = arr[lIndex++];
            }else {
                count += (mid - lIndex + 1);
                help[index++] = arr[rIndex++];
            }
        }
        // 此时上边循环结束，有两种情况。
        // 1：lIndex 越界
        // 2：rIndex 越界
        while (lIndex <= mid) {
            help[index++] = arr[lIndex++];
        }
        while (rIndex <= r) {
            help[index++] = arr[rIndex++];
        }
        // 最后把辅助数组给 拷贝到 数组里
        do {
            arr[r] = help[--index];
            r--;
        } while (r >= l);
        return count;
    }


    // for test
    public static void main(String[] args) {
        int[] arr = {2, 3, 5, 7, 1, 4, 6 ,8};
        System.out.println(reversePairs(arr));
        System.out.println(reversePairs2(arr));
    }

}
